Voidokilia to niemal idealny półokrąg piasku w kształcie greckiej litery omega, zamknięty z obu stron skalnymi cyplami. Nazwa znaczy mniej więcej „brzuch wołu”, od zaokrąglonego kształtu zatoki. Za plażą ciągną się wydmy, a dalej płytka laguna Gialova, oddzielona od morza wąskim wałem piasku. To jedna z najważniejszych ostoi ptaków w Grecji: w okolicy zanotowano 258 gatunków, w tym wiele zagrożonych, bo laguna leży na trasie wędrówek między Europą a Afryką. Na wydmach żyje kameleon afrykański, przez lata znany w Europie tylko stąd (od 2025 r. potwierdzono drugą populację, na północnym Peloponezie). Badacze uważają, że sprowadzono go tu dawno temu jako zwierzę domowe.

Okolica jest pełna Homera. Za „piaszczyste Pylos” z „Odysei” uważa się właśnie ten brzeg: Telemach przybija tu, gdy mieszkańcy składają na plaży ofiarę z czarnych byków dla Posejdona. Nad zatoką jest mykeński grób kopułowy, nazywany grobem Trazymedesa, syna Nestora. Na skale nad południowym cyplem otwiera się Jaskinia Nestora z wysokim sklepieniem i otworem w stropie. Pauzaniasz, podróżnik z II w. n.e., pisał, że Nestor i jego ojciec Neleus trzymali w niej bydło, a tradycja dodaje, że to tu mały Hermes ukrył krowy skradzione Apollinowi. Archeolodzy znaleźli w jaskini ceramikę od neolitu po epokę mykeńską.

Wyżej stoi Paleokastro, ruiny frankijskiego zamku z XIII w. postawionego na miejscu ateńskiego fortu z 425 r. p.n.e. Wtedy, w bitwie pod Pylos, Ateńczycy pod wodzą Demostenesa i Kleona zamknęli spartańskich hoplitów na wyspie Sfakteria i zmusili ich do kapitulacji, co wstrząsnęło całą Grecją: do niewoli poszło 292 ludzi, wśród nich 120 pełnoprawnych Spartiatów. Szczegółowo opisał to Tukidydes (ok. 460–ok. 400 p.n.e.), ateński wódz i historyk wojny peloponeskiej, nazywany ojcem historii krytycznej, bo szukał przyczyn wydarzeń w ludziach, a nie w woli bogów. Na tej samej zatoce Nawarino 20 października 1827 r. połączone floty Wielkiej Brytanii, Francji i Rosji zniszczyły flotę turecko-egipską, co przesądziło o niepodległości Grecji. Pylos świętuje rocznicę co roku jako Nawarinia, z regatami, tańcami i wieczorną rekonstrukcją bitwy na wodzie.