Wojna toczyła się dalej pomimo odejścia Peryklesa. Kiedy Ateny radziły sobie źle, niektórzy z jej sojuszników zaczęli skakać ze statku. W 428 r. p.n.e. miasto Mitylena na wyspie Lesbos zbuntowało się przeciwko Atenom. Odpowiedź Ateńczyków była brutalna. Najpierw wysłano flotę ateńską, by zablokować wyspę. Po kapitulacji Mityleny ateńska ekklesia głosowała za egzekucją wszystkich obywateli płci męskiej i sprzedaniem kobiet i dzieci w niewolę. Ateny wcześniej zrobiły wszystko, co możliwe, aby pielęgnować swoje relacje z sojusznikami. Skąd więc drastyczna zmiana w postępowaniu z Mityleną? Cóż, śmierć Peryklesa pozostawiła w ekklesii próżnię, którą wypełniło to, co ateńscy arystokraci nazywali „nowymi ludźmi”. Ci nowi ludzie nie wywodzili się ze starożytnych linii arystokratycznych, takich jak Perykles, i dostali się do wpływowych pozycji dzięki zdolności do podburzania motłochu i robienia imponujących przemówień w ekkleisie. Najważniejszymi z nowych ludzi byli Kleon i Hyperbolos. Hyperbolos był tak znany ze swojego mówienia, że słowo „hiperbola” wywodzi się od jego imienia, które dosłownie oznaczało „rzucanie poza” (to znaczy przesadzanie)! Obaj ci nowi mężczyźni często wygłaszali podburzające przemówienia, które zachęcały Ateńczyków do podjęcia najsurowszych działań. Odpowiedź na Mitylenę była tego przykładem. Chociaż Kleon twierdził, że Mitylena powinna zostać surowo ukarana, Ateny czuły się niekomfortowo z tym osądem. Kwestia ta była dyskutowana ponownie następnego dnia, a większość głosowała za lżejszą karą. Wysłano statek, aby odebrać wieści i przybył do Mityleny w samą porę, by powstrzymać masakrę. Uff! Nowi ludzie w Atenach są bezlitośnie wyśmiewani przez komicznego dramaturga Arystofanesa w jego sztuce Rycerze. Arystofanes szczególnie nienawidził Kleona, którego nazywał „garbarzem”, szydząc z jego doświadczenia w handlu wyrobami skórzanymi. W Osie poszedł jeszcze dalej, nazywając postacie „Procleon” i „Anticleon”. Procleon jest napisany jako totalna przechwałka, ale prawdziwy mięczak, jeśli chodzi o walkę:
„Tu, tutaj, co mnie czeka? Upadłem, nie mogę dłużej trzymać miecza w górze! Wyczerpała się ze mnie cała walka!”