Saxarna drogs till Bedfordshire när de invaderade England, eftersom området hade gott om vatten och var lämpligt för jordbruk. Det finns dock få lämningar av saxiska boplatser, och de lämningar som finns ligger med ett undantag söder om Great Ouse. Den viktigaste är en begravningsplats vid Kempston, där både brandgravar och kistgravar har hittats.
Tidiga referenser till Bedfordshires politiska historia är glesa. 571 besegrade Cuthwulf brittiska stammar vid Bedford och erövrade fyra orter. Under heptarkin tillhörde dagens Bedfordshire Mercia. Därefter tillföll det Danelagen, men återerövrades av Mercia under Edvard den äldre runt 920. Namnet Bedfordshire förekommer första gången 1011, då som Bedanfordscir. Grevskapet hade fram till 1574 gemensam sheriff med Buckinghamshire. 1016 ödelade Knut den store hela området. Det fanns inget organiserat motstånd mot Vilhelm Erövraren inom Bedfordshire, trots att Domesday Book beskriver en nästan fullständig ersättning av engelska jordägare med normandiska.
Bedfordshire led svårt under inbördeskriget mellan Stefan av Blois och Matilda. Under första baronkriget belägrades Bedfords slott tre gånger innan det förstördes på kungens order. Under denna period blev också fårskötsel en viktig näring. Bondeupproret 1377–1381 var mindre våldsamt i Bedfordshire än i granngrevskapen; Dunstablesannaler nämner kortfattat ett uppror där som ledde till att orten fick stadsrättigheter. Under engelska inbördeskriget stod grevskapet fast på parlamentssidan.
Politik
Det tidigaste omnämnandet av parlamentsledamöter från Bedfordshire är från 1290, då grevskapet skickade två ledamöter till Englands parlament. Idag har grevskapet sex ledamöter.
Bedfordshire är inte en viktig målpunkt i sig, men grevskapet passeras av många transportleder mellan London och Midlands samt andra platser norrut.
De viktigaste vägarna är de nord-sydliga M1, som i Bedfordshire har tre trafikplatser vid Luton och en vid Bedford, och A1, som passerar genom grevskapets östra del. Storbritanniens tre viktigaste nord–sydliga järnvägslinjer (West Coast Main Line, Midland Main Line och East Coast Main Line) passerar grevskapet, och det finns en tvärlinje mellan de två förra från Bletchley (i Buckinghamshire) till Bedford.