This study employs a random parameters binary logistic regression (LR) to characterize the impact of environmental and structural parameters on concrete highway bridge deck deterioration nationwide. Two specific gaps in the literature are addressed: (1) the use of a nationwide dataset for analysis, and (2) the implementation of a methodology to account for unobserved heterogeneity. A total of 3,262 bridge deck deterioration observations derived from the authors’ nationwide concrete highway bridge deck performance inventory (NCBDPI) database were used in this study. The deterioration rate (DR) was computed as the decrease in the concrete bridge deck condition rating (CR) over time. Bridge decks with deterioration rates (DR) below a certain threshold were categorized as the lowest deteriorated bridge decks (lowest DR) and decks with DR above a certain threshold were considered among the highest deteriorated (highest DR). The following variables were found to be significant in the final model: average daily truck traffic (ADTT), climatic region, distance from seawater, bridge deck area, age of bridge, type of design and/or construction, structural material design, deck protection, type of membrane, type of wearing surface, and maintenance responsibility. The results show that bridge decks with a high ADTT, age of bridge, bridge decks located in cold regions, and those that are close to seawater are associated with the highest DR group of bridge decks. Furthermore, the type of design and/or construction and maintenance responsibility play a role in decks being associated with highest DR.