Pierwsze wzmianki o Witosławiu pojawiły się w 1395 roku. Źródła pisane wspominają o niejakim Szamborze herbu Prawdzic z rodu Witosławskich, który   w czternastym wieku był właścicielem miejscowości Witosław i ziem do niej należących. Witosławscy przybyli do Polski z Niemiec w czasach wojen z Krzyżakami. Legitymowali się Herbem Prawdzic, który znamionował również tak zasłużone dla Polski nazwiska jak Bielscy, Gostomscy, Sarbiewscy czy Sierakowscy. Niewiadomo dokładnie kiedy i w jakich okolicznościach  Witosław przestał być ich własnością. Kolejnymi właścicielami Witosławia byli: przed rokiem 1539 Maciej Rynarzewski,  a po 1539 roku Maciej z Czasowa. W 1673 r. właścicielem Witosławia został Paweł Żychliński, a w 1744 r. Władysław Krzycki, natomiast w 1773 r. Józef Krzycki, a następnie Koczorowscy.
Na przełomie XV i XVI wieku następował bardzo szybki rozwój Witosławia związany  z gospodarczym rozwojem Krajny. Kwitła gospodarka agrarna, rozwijał się handel. Przez Nakło, Mroczę, Więcbork, Sępólno, Tucholę i Starogard Gdański wiódł jeden z głównych szlaków handlowych łączących Wielkopolskę z Gdańskiem, nazywany „via nova” w znacznej mierze przyczyniający się do rozkwitu tego regionu.
Chłopi z Witosławia uprawiali przede wszystkim żyto, w dalszej kolejności owies, pszenicę, jęczmień i groch, stosując przy tym system trójpolówki. Plony uzyskiwali dosyć niskie, sporo żywności w postaci warzyw dostarczały przyzagrodowe ogrody warzywne. W XVI i XVIIIw. W Witosławiu funkcjonowała karczma, młyn, rzemieślnicy. 
Kolejne lata świetności Witosławia przypadają na okres, gdy miejscowość należała do rodziny Koczorowskich. Za czasów Tertuliana Koczorowskiego miejscowość liczyła 15 domostw i 134 mieszkańców. W chwili jego śmierci Witosław Liczył 25 domostw, 365 mieszkańców, z czego 362 było katolikami, a cały majątek ziemski wynosił 1807 hektarów.
Miejscowość na tle okolic wyróżniała się tym, że zdecydowanie przeważała ludność polskiego pochodzenia. Do Witosławia należał w tym czasie folwark Witosławek i Orle.
W 1854 Adolf Koczorowski, syn Terturiana zorganizował pierwszą szkołę   w Witosławiu, miała ona program ograniczony do nauki czytania i pisania w dwóch językach, rachowania, religii oraz praktycznej nauki ogrodnictwa i sadownictwa. Koczorowscy wiele czasu i prywatnych nakładów przekazywali na rzecz szkoły. W budynku dawnej poczty prowadzona była przez siostrę zakonną ochronka dla dzieci, którą również współfinansowali Koczorowscy.
Do znacznego rozwoju Witosławia przyczyniło się także wybudowane przez Prusaków w 1892 roku połączenie kolejowe Nakło-Chojnice oraz budowa kolejki wąskotorowej, którą podjęto głównie z myślą o przewozie buraków cukrowych z okolicznych plantacji do cukrowni w Rudkach koło Nakła. 
Kolejnym ważnym wydarzeniem w dziejach Witosławia było powołanie tuż po odzyskaniu przez Polskę niepodległości w 1919 roku przez uczestników walk wyzwoleńczych Towarzystwa Powstańców i Wojaków, którego sztandar do dzisiaj znajduje się w muzeum Ziemi Krajeńskiej w Nakle nad Not. Na działalność witosławskich wojaków ówczesny właściciel Witosławia Karol Koczorowski przeznaczył niewielką działkę pod parkiem dworskim, gdzie powstała strzelnica. Odbywały się tam spotkania członków oraz zawody strzeleckie i jeździeckie. W zabawach uczestniczyły całe rodziny. Podczas II wojny światowej pan Anastazy Prusak z narażeniem życia przechowywał sztandar w drewnianej skrzyni zakopanej w ogrodzie, a następnie na strychu i w gołębniku. W czasie II wojny światowej gospodarstwo rolne Koczorowskich przejęli Niemcy,  a okoliczna ludność została zmuszona do pracy na rzecz III Rzeszy. Ostatni właściciel Witosławia, Franciszek Koczorowski zginął zaraz na początku II Wojny Światowej w 1939 roku. W sylwestra roku 1939/40 spaliła się część dworu, spłonęły wtedy meble i ogromna część archiwów, pozostałe przedmioty zostały rozkradzione. Po wojnie na podstawie reformy wywłaszczeniowej z 6 września 1944 roku część majątku rozparcelowano pomiędzy okolicznych mieszkańców, pozostała część została przekształcona w Państwowe Gospodarstwo Rolne. Byli pracownicy majątku, którzy wykupili ziemie od ówczesnych władz nie gospodarowali na nich długo, po pewnym czasie spora część rozparcelowanego majątku została ponownie przyłączona do PGR-u Witosław.  W Państwowym Gospodarstwie Rolnym zatrudnienie znalazło kilkuset mieszkańców Witosławia.
Lata powojenne to rozkwit Witosławia. W 1949 roku na terenie wsi założono bibliotekę  gminną, później pobudowano pierwszy na Pomorzu w powojennej Polsce Wiejski Dom Kultury, a w 1961 roku oddano do użytku szkołę 1000-latkę, ośrodek zdrowia, zakład mechanizacji i mieszalnię pasz. W latach 1990/91 nastąpiła likwidacja PGR.
Dzisiejszy przysiółek Witosławia to wieś Orle, wzmiankowana w 1288r.