L'unico riferimento preciso sulla vita di Melisso ci è tramandato da Plutarco (Plutarco, Pericle 26; Temistocle 2), che a sua volta cita Aristotele. Questi avrebbe affermato che Melisso aveva sconfitto Pericle nella guerra che opponeva Samo ad Atene. Sappiamo poco delle circostanze in cui questa battaglia navale sarebbe avvenuta; comunque questo riferimento consentirebbe di collocare Melisso intorno al 442 a.C. Apollodoro (DL IX, 24) pone la sua acme nell'Olimpiade 84 (444-441), proprio al tempo della vittoria su Pericle. La tradizione fa di Melisso un cittadino di Samo, figlio di Itagene. Era presentato come scolaro di Parmenide, ma anche di Eraclito (DL IX, 24).
Tutte le fonti che ne parlano sono concordi nell'attribuire a Melisse un solo scritto (DL I, 16). Simplicio lo cita con il titolo Sulla natura o sull'essere, osservando anche che evidentemente Melisse riteneva che la natura fosse l'essere (Simplicio, Commento alla Fisica 70, 16; Commento al De cacio 557, 10). Altrove si trovano indicati separatamente i titoli Sulla natura (Galeno, De elementis secundum Hippocratem I, 9; Commento al «De natura hominis» di Ippocrate XV, 5 Kùhn; Simplicio, Commento al De caelo 556, 25) o Sull'essere (Suda, s.v. «Meleto di Laro» 30A2 DK). E improbabile che il titolo o i titoli risalgano allo stesso Melisso. Si è voluto vedere in essi un precedente del titolo dell'opera di Gorgia; ma al massimo Gorgia può aver conosciuto lo scritto di Melisso con uno di quei titoli, senza che questo autorizzi ad attribuirlo a Melisso stesso.
Anche se non sappiamo nulla delle loro biografie, Parmenide e Zenone sono diventati, da Platone in poi, una coppia esemplare di maestro e scolaro. Ma è difficile immaginare un legame di scuola che unisca Melisso di Samo, il quale vive nell'area orientale del mondo greco in piena età periclea, a Parmenide e Zenone. Con lui l'eleatismo è già diventato un'entità intellettuale vaga e diffusa. Isocrate lo pone accanto a Parmenide, Zenone e Gorgia come autore di dottrine paradossali. E Polibo, genero di Ippocrate, nel trattato De natura hominis, dopo aver polemizzato contro coloro che, non medici, si affannano a identificare l'uomo e il tutto, chi con l'aria, chi con l'acqua, chi con la terra e chi con il fuoco, disputando più di parole che di fatti, dice che costoro «danno ragione a Melisso». Il significato di questo accenno non è sicurissimo, ma è possibile che anche qui Melisso apparisse un autore paradossale, al quale si finisce con il dar ragione a forza di dispute puramente verbali. Platone, forse con qualche ironia, dice che Melisso vale un po' meno di Parmenide. Ancora una volta Aristotele segue Platone considerando Melisso addirittura «rozzo». Parmenide e Melisso avevano entrambi svolto una teoria dell'uno, ma Parmenide lo aveva considerato «secondo la definizione», Melisso «secondo la materia, e per questo uno dice che è finito, l'altro infinito». Attraverso questo gergo aristotelico un punto pare effettivamente attribuibile a Melisso: la considerazione dell'uno come infinito. Questo è per Aristotele un errore di categoria, perché l'infinito spetta alla quantità, che è un predicato, e non alle cose che sono soggetti dei predicati. Le cose-soggetto sono sostanze, e le sostanze hanno un limite e sono finite: aveva visto giusto Parmenide che aveva considerato il tutto finito.
Tuttavia in Aristotele e in Simplicio è possibile cogliere una traccia del ragionamento di Melisso, indipendentemente dalle critiche aristoteliche. Per Melisso il tutto è ingenerato, perché prima del tutto non c'è nulla; e dal nulla non sarebbe derivato nulla. Se non è generato, il tutto non ha principio e, se non ha principio, non ha neppure fine, sicché sarà infinito. Per Aristotele Melisso commetteva un errore ricavando dalla proposizione (1) 'tutto ciò che è generato ha un principio' la proposizione (2) 'tutto ciò che non è generato non ha un principio'. Per Aristotele il termine 'principio' ha un significato generale, non riducibile a quello di 'inizio', che risulta nelle testimonianze su Melisso. Pertanto Aristotele ritiene che, se tutto ciò che è generato ha un principio, non tutto ciò che ha un principio è generato45. Probabilmente però Melisso mostrava che l'essere non è generato (perché non può derivare dal nulla) e che perciò non ha inizio né termine, usando così la proposizione (2) senza ricavarla dalla proposizione (1). Si comprende assai bene l'avversione di Aristotele per Melisso. La filosofia di Parmenide poteva apparirgli paradossale, lontana dalla realtà delle cose; ma essa sembrava stabilire che l'essere è limitato e perfetto, un caposaldo della concezione aristotelica del mondo come un tutto ordinato e finito. E anche per Zenone l'infinito era qualcosa di negativo. Melisso invece introduceva l'infinito nell'uno stesso e pretendeva che tutto ciò che ha un principio fosse generato. Il rischio era che un mondo dipendente da un principio, che ne garantisce l'ordine, diventasse generato e perdesse l'eternità: una cosa impossibile nella concezione aristotelica del mondo.
Dai testi trasmessi da Simplicio emergono però alcuni tratti della teoria dell'infinito di Melisso, che l'interpretazione aristotelica lasciava in ombra. Non solo Melisso attribuiva all'essere l'infinità di grandezza e l'eternità temporale, ma soprattutto doveva sviluppare una teoria dell'unicità dell'infinito. Se non fosse uno solo, l'infinito confinerebbe con qualche altra cosa, e perciò non sarebbe infinito: infatti non ci potrebbero essere due infiniti, perché essi si limiterebbero a vicenda. L'uno infinito è anche omogeneo, perché se subisse qualche mutamento non sarebbe più uno. Infatti se cambiasse non sarebbe più simile a se stesso, ma ciò che era prima non ci sarebbe più e ciò che non è nascerebbe: l'uno, cambiando, diventerebbe molti. E basterebbe che mutasse di un capello in diecimila anni, perché perisse completamente: in un tempo infinito una trasformazione, per piccola che sia, potrebbe coinvolgere tutto l'uno. Non esiste neppure il vuoto, che è non essere. L'assenza del vuoto determina la mancanza di movimento, perché l'essere non può spostarsi verso il nulla. Se esistessero i molti, ciascuno, per esistere davvero, dovrebbe essere come l'uno, e non potrebbe trasformarsi in uno degli altri o comunque mutare. Ma la percezione ci rivela anche trasformazioni e mutamenti, che invece non ci possono essere: perciò non ha vero essere quel che essa ci mostra. L'uno non ha neppure corpo, perché il corpo è divisibile in parti. Se fosse divisibile in parti, queste renderebbero possibile il movimento, e il movimento introdurrebbe il non-essere.
Si è fatto con Melisso quello che Platone aveva tentato con Zenone: si è supposto che egli conducesse una polemica. I suoi avversari sarebbero ora i pitagorici, ora Empedocle. Ma si tratta di congetture non corroborate da riscontri attendibili. Si è cercato però anche di collegare Melisso con Anassagora, attribuendogli una teoria della completa uniformità dell'essere, oppure con gli atomisti attraverso la sua concezione del vuoto. Ma Anassagora non nega il movimento e gli atomisti ammettono il vuoto. Anche qui siamo del tutto privi di notizie specifiche, e nel caso di Melisso diventa anche più difficile immaginare i rapporti di scuola che secondo Platone avrebbero legato Zenone a Parmenide.
Con un puro confronto di testi è possibile scorgere in Melisso alcuni temi originali all'interno della cultura eleatica. Attribuisce all'uno la durata temporale che Parmenide nega all'essere e, mentre Parmenide immagina l'essere come finito e limitato, Melisso lo considera infinito, proprio perché non ha né inizio né fine e si estende senza limiti. Forse perfino l'unità dell'essere e motivo propriamente Melisseo, e lo è certamente la dimostrazione dell'unicità dell'infinito, che avrà molta fortuna nella tradizione filosofìca. Si potrebbe dire che Melisso ha cercato di limitare l'ordine dell'infinito, evitando che si formassero infiniti di infiniti, oppure che ha cercato di introdurre l'infinito escludendo il continuo; ma sarebbero elucubrazioni. Probabilmente si tratta di schemi argomentativi usati da Melisso: se si ammette una molteplicità, ogni suo elemento si configura come un essere unitario, e dunque infinito; ma più infiniti sono impossibili. Forse Zenone argomentava che se c'è molteplicità c'è infinità e dunque una serie di proprietà contraddittorie. Per Melisso l'infinito in quanto tale non crea difficoltà e può essere attribuito all'uno; però, se c'è molteplicità, c'è sempre più di un infinito, e questo è impossibile.