Erstmals wird Samara in einer russischen Chronik aus dem Jahr 1361 erwähnt. Auf einer 1367 erstellten Karte der Wolga der venezianischen Kaufmänner Francesco und Dominico Pizzigano ist eine Siedlung Samara gekennzeichnet. Nach einem Befehle des Zaren Fëdor Iwanowitsch begann im Jahre 1586 an der Wolga bei der Mündung des breitesten Arms des Flusses Samara der Bau einer Bewachungsfestung, die "Samara-Städtchen" genannt wurde. Diese Festung sollte den Schutz gegen die Angriffe der Nomaden auf Russland, sowie für den Wasserweg von Kasan nach Astrachan gewährleisten. Die Festung wurde unter der Leitung des Heerführers Grigory Osifowitsch Sassekin an der Stelle des heutigen Chlebnaja-Platzes (Brotplatzes) errichtet. Am Anfang wurden die Mauern aus zugespitzten Holzstämmen und Wachtürme mit Schießscharten ausgeführt; danach der Kreml, eine Kirche und schließlich Wohn- und Wirtschaftsgebäude für die künftige Bevölkerung. 1636 war die Festung bereits 1700 Meter lang und 350 Meter breit. 1689 wurde das Städtchen offiziell zur Stadt. Zu diesem Zeitpunkt war Samara nicht mehr nur wichtiger Militärstützpunkt, sondern auch großes Handelszentrum als Umschlagplatz des russischen Handels mit dem Orient geworden. 1708 galt Samara als neuntgrößte Stadt des Kasaner Gouvernements, wurde ab 1719 zum Astrachaner Gouvernement gezählt. Damals hatte die Stadt 210 Höfe. In dieser Periode geriet sie ins Epizentrum zweier Bauernaufstände. Im Jahr 1670 wurde Samara vom Heere des Stepan Rasin erobert, und im Jahr 1773 war Samara die erste Stadt, die auf die Seite des Jemeljan Pugatschow übertrat.