W następnym roku Olson spróbował sił w wadze półciężkiej. 13 kwietnia 1955 w San Francisco wygrał na punkty z byłym mistrzem świata Joeyem Maximem a 22 czerwca w Nowym Jorku spróbował odebrać tytuł mistrza świata Archiemu Moore’owi, ale został znokautowany w 3. rundzie. 9 grudnia tego roku stracił tytuł w wadze średniej po przegranej przez nokaut w 2. rundzie z powracającym po ponad dwuletniej przerwie Sugar Rayem Robinsonem. Kolejna walka z Robinsonem o odzyskanie tytułu zakończyła się znokautowaniem Olsona w 4. rundzie 18 maja 1956 w Los Angeles.
Po tej porażce Olson pauzował przez ponad rok. Powrócił na ring w czerwcu 1957 wygrywając ponownie z Joeyem Maximem. Walczył głównie w wadze półciężkiej, choć niekiedy w ciężkiej. Wygrał wszystkie walki w 1958 i 1958, a w 1960 pokonał go tylko Doug Jones. W 1961 zwyciężył 5 razy i raz przegrał, a w 1962 wygrał trzy walki, przegrał jedną (z Pete’em Rademacherem) i 1 zremisował (z Giulio Rinaldim). W 1963 wygrał 4 walki i 1 zremisował. 27 listopada 1964 w Madison Square Garden stoczył walkę eliminacyjną przed pojedynkiem o tytuł mistrza świata w wadze półciężkiej, ale przegrał przez nokaut w 1.