Here are the cheapest hostels with good ratings and private rooms: New Art Hostel Can Rubi Urban Hostel Palma We highly recommend booking your accommodation in advance, because Palma de Mallorca is the starting point for all travelers and hotels are quite fast fully booked.