Ya en el siglo X cruzaba el río Moldavia un puente de madera ubicado apenas unos metros más al norte del actual Puente de Carlos. No era lo suficientemente resistente, siendo más bien una pasarela, así que no aguantó la fuerza de la inundación de 1157 y se hundió.
Entre los años 1160 y 1172, el rey Vladislao II hizo construir el primer puente de piedra en Praga, siguiendo la sugerencia de su esposa Judit, en honor a quien fue nombrada la nueva construcción. Tenía alrededor de 514 metros de largo y hasta 7 metros de ancho, y se sustentaba sobre 27 arcos bajos. En el año 1253 la custodia del puente pasó a manos de la Orden de los Caballeros de la Cruz. En febrero de 1342 dos terceras partes del puente se cayeron por causa del deshielo, de manera que la construcción hubo de ser reemplazada por una nueva el Puente de Carlos.
Hasta nuestros días se han conservado restos de arcos del Puente de Judit en sótanos de algunas casas, los fundamentos de pilones en el fondo del Moldavia y la menor de las torres del puente de Malá Strana. Dicen que la llamada estatua del "Barbilla" asentada en el muro del Puente de Carlos de nuestros días, retrata al constructor de Puente de Judit, y además sirve de marcador del nivel de agua del río. La antigua torre del Puente de Judit está hoy en el recinto del monasterio de la Orden de los Caballeros de la Cruz (Museo del Puente de Carlos en la actualidad).
El Puente de Carlos fue en su época apenas el cuarto puente de piedra en construirse en el Reinado de Bohemia, después de los de Písek, Roudnice y el arriba mencionado Puente de Judit. Está acodado tres veces a su largo y resulta poco prominente con respecto al tamaño de la corriente.
Puesto que el puente está todo colocado sobre una base rocosa, sus pilares fueron construidos sobre pilotes de madera de roble que están afianzados mediante piedras molares. Un sondeo del siglo XIX confirmó que las piedras molares están unidas por grampas de hierro cubiertas de plomo. Los tajamares del lado de la corriente son aparentemente más agudos y la protección que ofrecían era incrementada por rompehielos de madera. En el medio del puente el pavimento se hizo un poco más alto para que el agua de lluvia se desaguara por los canales laterales. Para la construcción del puente se usó arenisca granigruesa y los cantales fueron sujetados con un mortero extremadamente fuerte. La leyenda cuenta que los constructores del puente añadían huevos al mortero; la ciudad de Velvary quiso aportar con un envío, pero para ir a la segura y no romperlos durante el transporte, los cocinaron, inutilizándolos así para su propósito.
El primer constructor del puente fue el maestro Otto, llamado también Otlín. En los años 60 del siglo XIV la obra pasó a manos de Petr Parlér, quien la continuaría hasta su muerte en 1397.
Již deset let po zahájení stavby, v roce 1367, pobořila velká voda pilíř rozestavěného mostu. Apenas diez años después del inicio de la construcción, o sea en 1367, una creciente derrumbó un pilar de la obra. Tanto durante la construcción como después de terminada esta, el puente se vio repetidas veces amenazado por las inundaciones (1359, 1367, 1370, etc.), las cuales ocasionaron muchos daños irreparables. En la gran inundación de 1432, durante la cual también quedó bajo el agua la mayor parte de la Ciudad Vieja, el puente se abrió en tres puntos y cinco pilares quedaron gravemente dañados. La reconstrucción duró unos inimaginables 71 años, o sea hasta el año 1503. Nuevos pilotes fueron hincados manualmente con martinetes. Otra catástrofe para el Puente de Carlos sobrevino en el año 1784, cuando varias balsas y bloques de hielo se atascaron en los arcos, y el agua derruyó los pilares sobre los que se hallaba la garita de la guardia militar. Una situación similar ocurrió en 1890, cuando quedaron atrapados bajo el puente troncos de madereros que batían los pilares. Uno tras otro cayeron el quinto, el sexto y el séptimo pilar (visto de la orilla de Malá Strana). Durante la siguiente reconstrucción se usó un método diferente: los pilares fueron puestos sobre las llamadas campanas sumergibles de hierro. Este método se aplicó también para el refuerzo de los otros pilares del puente. Entre los años 1965 y 1978 el puente pasó por la última reconstrucción completa que costó en aquel entonces unos 50 millones de coronas. Se cambiaron todos los cantales dañados, y la superficie de asfalto de los años 20 del siglo pasado fue reemplazada por un enlozado de piezas de granito. Desde el año 2001 se está planeando la reconstrucción de la parte superior y de los arcos del puente.