Есть и еще одно предание. Две сестры-сирены плыли из Балтийского моря. Одна из них поплыла к Дании (та самая знаменитая Русалочка Андерсена), а вторая через Гданьск по Висле приплыла к тому месту, где сейчас находится Старый город. Здесь располагалась рыбацкая деревушка. Она осталась и пела рыбакам свои песни. Но однажды ее поймал купец, чтобы показывать на ярмарке за деньги. Плач русалки услышал молодой рыбак и освободил ее. В благодарность она обещала всегда приходить на помощь жителям Варшавы.
Историки же считают, что город возник, когда здесь появился замок наместника мазовецкого князя. В небольшое поселение вокруг замка переехала богатая и знатная чешская семья Варшев, которая, избегая гонений на родине, отправилась сюда вместе с многочисленной дружиной. Именно эти люди и были основателями Варшавы. Пределы Старого города (Старувки) в какой-то момент стали тесными для горожан, и они основали Нове Място. На месте старого языческого храма был выстроен костел Пресвятой Богородицы. Вокруг него стали возводить дома крестьяне.
Первые письменные упоминания о будущей столице Польши датируются 1313 г. Более же обширная информация содержится в судебном деле против Тевтонского ордена, слушание которого проходило в варшавском соборе Святого Иоанна в 1339 г. В начале XIV в. Варшава уже была одной из резиденций мазовецких князей, а в 1413 г. официально стала столицей Мазовии. Здесь открывались фабрики и лавки, строились водяные мельницы, появился большой рынок. Город обустраивался, и расширялись его границы. В 1515 г. в ходе Русско-литовской войны большая часть Старого города была сожжена. А в 1526 г. Мазовия, включая Варшаву, вошла в состав Польского королевства, что способствовало будущему процветанию города. В 1529 г. в Варшаве впервые собрался польский сейм.
В 1596 г. Варшава стала столицей не только Польского королевства, но и Речи Посполитой. Впоследствии город неоднократно осаждали и грабили многочисленные враги, Варшава пережила наводнения, эпидемии и неурожаи, однако, несмотря ни на что, продолжала строиться и развиваться.
Варшава оставалась столицей Речи Посполитой вплоть до окончательного прекращения ее существования в 1795 г., после чего была присоединена к Пруссии. В 1806 г. войска Наполеона вошли в Варшаву, и город стал столицей Варшавского герцогства (под французским протекторатом), а после Венского конгресса 1816 г. – столицей Царства Польского, находившегося под властью Российской империи. К концу XIX в. Варшава была третьим по величине городом империи – после Санкт-Петербурга и Москвы.