Tracce di vita preistorica neolitica sono emerse in località Bottino, dove sono state rinvenute lamelle di selce e ceramiche, in località San Vito sono stati ritrovati: oggetti di bronzo, lame e frecce di selce dell'età del bronzo.
È l'epoca romana quella che ha lasciato maggiormente tracce nell'area di Casaloldo. In antico l'attuale territorio del paese non era esclusivamente pertinente all'agro di Mantova, ma parte era compreso in quello veronese, parte in quello cremonese, ed in parte nell'oltrepò ed afferiva all'Emilia.

Tra i più interessanti reperti archeologici del periodo romano recuperati in Casaloldo, si segnala una pregevole applique bronzea a soggetto mitriaco databile attorno al I sec. d.C. (1) e un balsamario in argento e oro a maschere teatrali sempre di età imperiale (2).
Questi reperti oggi rappresentano il vanto del Museo Archeologico di Mantova. Dal IX sec, al XIII sec. d.C. Casaloldo unisce le sue fortune a quelle di una importante famiglia: i Conti Longhi da Casalalto o Casalodi. Casaloldo vede inoltre la sua storia legata a quella dei paesi vicini, in particolare Asola e soprattutto Castelnuovo di Asola, in alcuni periodi del passato. Oggi sappiamo che Casaloldo in origine, si chiamava Casalto, Casale Alto (Casalis Altis), Casalzucco o anche Casalatto, sorgeva come afferma l'Amadei "tra due munitissime torri con un castello" di cui vi sono ancora visibili alcuni resti. Il Mangini, cancelliere della Serenissima, nelle "Flistorie" fa discendere la stirpe dei Casalodi da Brenno re dei Galli-cenomani, scesi in Italia nel V secolo.
Il nome del casato Io incontriamo però ufficialmente solo nel 964 allorché Ermengarda, moglie di Corrado da Verona lascia un legato per una cappella da erigersi in "Locus Dicituri Casalis Altis".

Un altro storico il Muratori, da per certa la notizia delle armate di Matilde sconfitte il 15 di Ottobre 1080 a Volta Mantovana dalle truppe imperiali, mentre il Mangimi assicura che questa battaglia si sia svolta in località san Vito di Casaloldo e che per tale scontro Mantova è stata sottratta alla contessa.
Non è semplice stabilire l'origine di questa famiglia ma la autorevole affermazione sembra essere quella di Odorici il quale afferma che la famiglia dei Longhi appartenga alla stirpe degli Ugoni secondo alcuni e per altri fu Laffranco I Conte di Casaloldo a dare origine alla famiglia.

È certo che Lanfranco Conte di Casaloldo fu padre di Azzone I, Vizzolo e forse Narisio, questi fratelli ebbero ciascuno successione. Azzone si chiamò Conte di Mosio, Vizzolo Conte di Sarazzino e Narisio Conte di Montechiaro, Alberto, figlio di Azzone conservò l'antico titolo di Conte di Casaloldo, Ugo suo fratello divenne Conte di Redondesco Pizone, Pizino o Pizio Conte di Marcaria. Quella dei Longhi fu la famiglia più potente tra quelle dei conti rurali stanziati nel territorio tra Cremona, Mantova, Brescia e Verona.
Il castello dei Casalodi nell'anno 1214, era tanto poderoso per mezzi e per soldati che i Conti potevano aspirare alla conquista di Brescia. Casaloldo fu a lungo in guerra con Asola.

Questa fu conquistata da Rotario di Casaloldo neI 1121. Intervenne poi Brescia a punire i Casalodi. Ridusse al suolo il castello nel 1125, ma l'operazione facilitò i Casalodi, che nel 1150 ricostruirono rocche e torri ed ebbero dall'imperatore Rotario nel 1155 l'investitura ufficiale. Brescia nel 1147 invase di nuovo l'asolano e pose d'assedio Casaloldo. Il risultato fu che i Longhi, due anni dopo tentarono addirittura di impadronirsi di Brescia e furono respinti a stento.
Nel 1158 rincominciarono le scorrerie e le battaglie; fu allora che Brescia decretò che nella stessa terra dei Casalodi si levasse un castello e vi fosse mercato franco (oggi Castelnuovo di Asola).
Il nuovo borgo a ridosso di Casaloldo prese il nome "Costrum Novum" ed era esente da ogni tassa. Questo mercato franco portò il popolo di Casaloldo alla rivolta. Nel frattempo Brescia era andata conquistando attorno terre e castelli così da chiudere in una morsa il borgo ribelle. Fu la rovina; Casaloldo fu costretto a vivere in un piccolo spazio limitato in ogni iniziativa affamato ed indebolito. Con la forza della disperazione il popolo nel 1181 assediò e poi prese il castello di Brescia. Lo lasciò solo quando questo fu completamente depredato.

Il popolo di Casaloldo fu inseguito dai rinforzi e fu decimato, furono distrutti ed incendiati i cascinali, il borgo e i raccolti, i bresciani però non riuscirono ad espugnare il castello. Alberto signore Conte di Casaloldo non si diede per vinto; dopo essere stato cacciato da Brescia si fece dì nuovo pericoloso riuscendo nel 1211 ad entrare in Brescia divenendone il podestà. Sembra che lo stemma araldico della Città di Brescia (la leonessa) derivi da quello dei Casalodi (il leone rampante).
Nello stesso anno ottenne dall'Imperatore Ottone IV anche i possedimenti di Lonato, Custoza, Isola della Scala e Gonzaga. Fu proprio quest'ultimo il possedimento più difficile da gestire. Gonzaga spettava al Papa Innocenzo III per testamento di Matilde, ma Alberto lo tenne per sé scontrandosi con Mantova e con Cremona. Al rifiuto di restituire quel territorio, Federico II imperatore per rendere giustizia alla Santa Sede promulgò nel 1220 l'Imperiale Decreto con bando di confisca dei beni di Alberto dei suoi successori ordinando nello stesso tempo a mantovani, bresciani, veronesi e ferraresi di non prestare aiuto ai Conti di Casaloldo e invitando Parma, Reggio, Modena e Bologna a muovergli guerra.

Nel 1269 viveva a Mantova Pinamonte da Bonacolsi, uomo scaltro, che desiderava il governo della città, fattosi amico Federico Conte di Marcaria, utilizzò i Casalodi, cioè Alberto di Casaloldo (nipote del precedente) per far nascere una rivolta e farsi eleggere rettore insieme a Federico, ma nel 1272 si liberò di loro, facendo insorgere il popolo con false accuse e facendosi nominare capitano e reggitore assoluto di Mantova. Confiscò tutti i beni dei Casalodi a vantaggio della propria famiglia, ed è a questo fatto che allude Dante Alighieri nei versi:
"Già fur le genti sue dentro più spesse
Prima che la mattia dì Casalodi
Da Pinamonte inganno ricevette".
Nel secolo XIV il paese subì la parziale distruzione ad opera delle bande armate di Reggio Emilìa. Casaloldo poi passò a far parte della "Quadra" di Asola prima con i Gonzaga e poi con la Serenissima Repubblica di Venezia.

Dopo la pace di Cavriana del 20 novembre 1441, conclusa tra Milano e Venezia, Il Marchese di Mantova mosse lite per riavere a se il territorio strategico di Casaloldo oramai passato ad Asola, ma il Doge non acconsentì e il borgo dovette trascorrere un periodo di inquietudini finendo nel 1447 sotto Brescia; poi nel 1453 sotto Mantova ed infine ancora sotto il distretto veneto subendo la condanna; in pena alla ribellione fu costretto a pagare i lavori di ricostruzione della rocca e della rocchetta Asolana.
Il 1509 fu un anno memorabile per Casaloldo, poichè dopo una guerra molto cruenta il borgo riuscì finalmente a trovare una lunga pace. I marchesi di Mantova avevano sempre desiderato il possesso di Casaloldo per ragioni strategiche: nel maggio 1509 decisero di sferrare un poderoso attacco; il Provveditore Veneto di Asola lo seppe però in tempo e inviò sul posto 600 cavalieri tra i più esperti, la battaglia durò due ore e si svolse a Sant'Emiliano dove oggi è allocato il cimitero. Così mentre gli asolani affrontavano i nemici, i contadini di Casaloldo con picchi, tridenti, falcetti lì strinsero alle spalle costringendoli ad una fuga precipitosa; Mantova lasciò sul terreno morti, feriti, prigionieri, 4 pezzi d'artiglieria di bronzo, archibugi e munizioni; il Doge mandava ampia lode ai vincitori della battaglia, ricordata nel grande quadro della chiesa parrocchiale (copia settecentesca dell'originale oggi in Palazzo Ducale a Venezia).

Il paese sotto la garanzia di Venezia si poteva ora dedicare alla ricostruzione.
Nel 1629 venne dato l'ordine di dare la "caccia ai luridi Alemanni" che portavano con infiltrazioni isolate la peste tra la popolazione. Ai Lanzichenecchi risale infatti la Maria dei Crocioni, chiesetta eretta a suffragio delle tantissime persone morte di peste e sepolte in una enorme fossa comune.
Anche allora il paese si era ripreso e, tranne lo scompiglio portato dai Tedeschi nel 1714, la pace durò fino al 1797 e più avanti sino alla scaramuccia del 24 giugno 1859 fra retroguardie Franco-Piemontesi e i reparti Austriaci durante la battaglia di Solferino-San Martino.
L'antico borgo, sostituito in contrade era stato costretto alla "incastellazione", a fare cioè da corona al maniero dei padroni e steso a protezione degli ingressi della loro casa.
Nonostante il Cardo (la via pubblica) e il Decumano (l'asse del Tartaro, fiancheggiato da strada) di sicura impostazione romana siano rimasti leggibili, ben poco è rimasto del castello che le cronache ricordano di disegno stupendo e di ottima costruzione, a cui si accedeva per un lungo ponte come quello di San Giorgio a Mantova.

Il castello sicuramente costruito nella parte frontale con muri solidissimi e in mattoni a vista e da palizzata per la restante parte, rimase in piedi fino all'inizio del 700 quando fu smontato per permettere con il riutilizzo dei mattoni la costruzione della chiesa e dell'imponente campanile. Nel portale d'ingresso gli archi, lo spacco per le catene del ponte, l'ingresso pedonale, lo spiraglio e i piombatoi, la feritoia e la fessura per la calata della saracinesca sono oggi i resti del castello. Vi è poi alla sommità una serie di archetti pensili in cotto e qualche squarcio di affresco con l'arma del casato, figure votive e all'esterno festoni di fìori e di frutta, parte della volta della chiesetta del castello (oggi scomparsa) fu imbragata e posta in una cappella laterale della chiesa parrocchiale. Nella bassa torre d'ingresso hanno ricavato negli anni settanta alcune stanzette d'abitazione. L'ultima torre superstite è stata modificata e adattata a cella del capannone civico, asportato durante la guerra e rifatto nel 1946.
Sopravvissuta miracolosamente al logorio del tempo rimane, sul fronte del portale d'ingresso al castello, la enigmatica coppia di "mattoni parlanti" a testimoniare un passato ancora pieno di mistero.
Altra costruzione di una certa importanza è il Teatro della Società Operaia di Mutuo Soccorso, recentemente restaurato, ora mostra, finalmente, il suo soffitto decorato con fregi, festoni, simboli teatrali e la ricorrente immagine delle due mani in solidarietà significanti il mutuo soccorso, era stato costruito nei primi anni del ventesimo secolo.
Anche Villa Fario è una costruzione di un certo valore, risale al XXVIII secolo e si trova sulla strada per Castel Goffredo.
Da ricordare anche gli edifici di culto:
· La Chiesa parrocchiale del secolo XVII con l'imponente campanile
· La Chiesetta dei Disciplini del secolo XVI
· La chiesetta di S.Vito del secolo XV
· La chiesetta di Molinello del secolo XVI
· La chiesetta dei Morti dei Crocioni del secolo XVI
Inoltre un particolare nota merita la corte di Molinello risalente alle zie di San Luigi Gonzaga Cinzia, Olimpia e Gridonia che fu ingrandita nel 600 e destinata dalle Vergini Gonzaga a convento.