První písemná zmínka o obci pochází z roku 1376, kdy je v městské knize z Bělé pod Bezdězem jmenován rychtář Nýček z Provodína.

Již v této době asi vesnice patřila k jestřebskému zboží Berků z Dubé a zůstala jejich majetkem až do poloviny 15. století. Syn Jindřicha z Dubé, husitského hejtmana v České Lípě, Čeněk, se tehdy zúčastnil na straně severočeské šlechty války proti lužickým městům. Roku 1445 byl za výpravy Lužičanů do Čech oblehnut hrad Sloup a s Lužičany spojená vojska litoměřické hotovosti se chystala také proti Jestřebí. Čeněk z Dubé raději prodal Jestřebí s příslušným panstvím veliteli litoměřické hotovosti Janovi ze Smiřic. Janovi synové Václav a Jindřich udrželi panství do 80. let 15. století, kdy je prodali Kryštofovi z Vartenberka. Roku 1545 získal jestřebské panství Kryštofův syn Václav z Vartenberka, který je připojil ke svému rybnovskému, později novozámeckému panství.

Novozámecké panství bylo majetkem Vartenberků až do třicetileté války. Jan Jiří z Vartenberka se aktivně zůčastnil protihabsburského povstání a proto mu bylo panství roku 1622 zkonfiskováno a o rok později je koupil Albrecht z Valdštejna. Po jeho smrti v Chebu roku 1634 mu byly jeho statky zkonfiskovány, pouze novozámecké panství bylo ponecháno vdově po zavražděném, Isabelle z Harrachu. Dědictvím přešlo roku 1654 na dceru Marii Alžbětu, provdanou za hraběte Rudolfa z Kounic. Tím se stalo novozámecké panství majetkem Kouniců a  zůstalo jím až do 20. století 

Již ve středověku byl Provodín pro svou rozlehlost rozdělen na dvě části, nazývané Provodín hořejší a Provodín dolejší, zda měla každá část svého rychtáře však zůstává neobjasněnou otázkou. Obyvatelstvo se živilo zemědělstvím, řemesla se zřejmě soustřeďovala v blízkém městečku Jestřebí. Za třicetileté války procházelo přes Provodín několikrát vojsko, obec byla částečně vylidněna a vypálena, počet obyvatelstva se snížil. V poválečném období se vrchnosti snažily, velmi často bez větších investic do hospodářství, dosáhnout co nejdříve maximálních zisků ze svých panství. Tento stav vedl roku 1680 k selskému povstání, kterého se intenzivně zúčastnili právě poddaní z Jestřebí a Provodína.