I used to go to Greece in the preseason and rooms to let was normally very easy (just go to the harbor or walk through some city and plenty of options available).
I wonder if this is true also for Malta in half/end September period?
To bring this question to an answered state, I have a good friend in Malta who lives in Valletta and has a vacation flat in Birzebbugia. I put the question to her exactly as you asked it.
Presumably by 'city' and 'harbour' you mean Valletta. You cannot rely upon walking through the city to find vacant rooms. You may luck out or may not, but in Valletta the odds are against you. In the other cities you may need a working knowledge of Maltese to read the signs outside the smaller B&B type of lodging opportunities.
On the plus side, if one proprietor takes you in, then you are pretty well set for the rest of Malta with their referrals.