Die ältesten Spuren einer Besiedlung der Umgebung von Bielsk Podlaski stammen aus dem 2. Jahrhundert v. Chr. – sie wurden in der Ortschaften Haćki und Hryniewicze Duże entdeckt. Dennoch ist gerade Bielsk Podlaski zum Zentrum dieser Gegend geworden. Auf dem Schlossberg in Bielsk hat man die Überreste eines Schlosses aus dem 10. und 11. Jh. gefunden. Weitere Forschungen haben bestätigt, dass sich an diesem Ort eine hoch entwickelte Stadt befand.
Die erste urkundliche Erwähnung von Bielsk Podlaski stammt aus dem Jahre 1253 (Galizisch-Wolhynische Chronik). Die nächste auftauchende Notiz über Bielsk betrifft eine Schlacht zwischen russischen Fürsten und den Jatwingern, die 1264 in der Nähe von Bielsk Podlaski stattfand. Nach 1320 gehörte die Stadt dem Großfürstentum Litauen an. Die Lage von Bielsk Podlaski verbesserte sich, nachdem Władysław II. Jagiełło den polnischen Thron bestieg. Die Stadt lag auf der viel bereisten Strecke von Kraków (Krakau) nach Grodno und Vilnius (Wilna).
Das 16. Jahrhundert erwies sich als sehr vorteilhaft für die Entwicklung der Stadt. Lokale Adlige, vor allem die Familie Sieheniewiczów, trieben hauptsächlich mit Holz und Gerbwaren mit Gdańsk (Danzig) durch den Hafen in Narew Handel. Die Bevölkerungszahl ist damals deutlich gestiegen: in der zweiten Hälfte des 16. Jahrhunderts zählte Bielsk Podlaski etwa 4-5000 Einwohner. 1564 erlebte die Stadt dramatische Stunden. In der Zeit des Litauischen Seimas, an dem Sigismund II. August teilnahm, brannte das hölzerne Schloss ab. Einige Jahre nach dem Brand gehörte die Stadt der Polnischen Krone an. Sie zähle damals über 550 Häuser und war die größte Stadt in Podlachien. Ein großer Brand im Jahre 1591 zerstörte die meisten Gebäude in Bielsk
Mehrere Kriege in den Jahren 1655-1660 sorgten für einen wirtschaftlichen Niedergang der Stadt und forderten viele Todesopfer. Nur einige Dutzend Häuser in der Stadt blieben bewohnt, das Handwerk kam beinahe völlig zum Erliegen. Kriege und Seuchen Anfang des 18. Jahrhunderts schwächten die Stadt ausgerechnet während einer Phase des Aufschwungs weiter. In den Jahren 1779-1781 wurde die königliche Kommission Boni Ordnis (der Guten Ordnung) eingesetzt, die die Stadt und ihre ländliche Vorstadt genau beschrieb und versuchte, viele lokalen wirtschaftliche und soziale Probleme zu lösen. Eine von der Kommission durchgeführte Überprüfung wies 269 bewohnte Grundstücke und 97 Handwerker auf. Zur zahlreichsten Gruppe gehörten die Gerber und Kürschner.
Ab 1807 unterstand Bielsk Podlaski dem Russischen Kaiserreich. 1897 zählte die Stadt bereits 8.400 Einwohner. In der Stadt waren eine öffentliche Schule, einige Pfarrschulen, vier russisch-orthodoxe Pfarrbezirke, ein römisch-katholischer Pfarrbezirk und einige Synagogen vorhanden.
1915 verließ die Hälfte der Einwohner Bielsk Podlaski infolge der Kriegshandlungen und floh (sog. Bieżeństwo aus den westlichen Gouvernements des Russischen Kaiserreichs ins Innere des Landes im Jahre 1915). 1930 zählte die Stadt knapp 6.352 Einwohner, 1939 waren es schon 8.200 (40% von ihnen waren Juden, deren Hauptbeschäftigungen im Handel und Handwerk lagen). Nach dem Ausbruch des Zweiten Weltkriegs waren öffentliche Institutionen noch bis zum 6. September 1939 in Betrieb. Eine Woche später marschierten deutsche Truppen in die Stadt ein, um dann am 23. September vor den sowjetischen Streitkräften zurückzuweichen. Am 22. Juni 1941 wurde die Stadt erneut von deutschen Truppen eingenommen. Während der Besatzung ermordeten die Deutschen ungefähr 800 Polen (u.a. Lehrer, Beamte, Pfarrer) im sog. Las Pilicki (Pilicki-Wald) und richteten ein Ghetto für Juden in der Mickiewicza-, Kazimierzowska-, Jagiellońska- und Kopernik-Straße ein. Das Ghetto wurde am 2. November 1942 aufgelöst. Die Mehrheit seiner Bewohner kam im Vernichtungslager Treblinka ums Leben.
2008 zählte Bielsk Podlaski 27.787 Einwohner.
