Незабаром після того, як патрульні катери типу «Етек» надійшли на озброєння ВМС Австралії, стало ясно, що вони занадто малі для ефективного вирішення завдань, що стоять перед ними. Тому у вересні 1977 року було оголошено, що катери типу «Етек» будуть замінені починаючи з кінця 1970-х років такою самою кількістю ПКА типу «Фрімантл».
Нові катери створені на основі проекту PCF-420 британської компанії «Брук марін» (м. Лоуестофт), яка і побудувала перший катер, введений до бойового складу флоту у 1980 році. Інші 14 (з 19 планувалися) будувалися на судноверфі компанії NQEA (North Queensland Engineers and Agents) в м. Кернс і були передані флоту з березня 1981 по грудень 1984 року.До складу катерів цього типу входять “Фрімантл”, “Уорнамбул”, “Таунсвіл”, “Вуллонгонг”, “Лонсестон”, “Уайалла”, “Іпсвіч”, “Сіснок”, “Беїдіго”, “Голер”, “Джералдтон”, “Даббо”, “Джилонг”, “Гладстон” і “Банбері”. Будівництво ПКА «Балларат», «Мілдьюра», «Армідейл», «Бандаберг» та «Пірі» було скасовано.Передбачалося, що термін служби цих катерів становитиме 15 років. Пізніше його збільшили до 19 років, а потім ще більше. Це стало можливим завдяки планово-попереджувальним ремонтам та модернізації, в ході якої, зокрема, було встановлено систему РЕБ.Спочатку катери цього типу були оснащені третім валом, з’єднаним із 12-циліндровим дизельним двигуном фірми «Дорман», який забезпечував рух у крейсерському режимі (дальність плавання при швидкості ходу 8 уз складала 5500 миль). Пізніше цей елемент ЕУ було демонтовано. Основним озброєнням катера є вже далеко не нова 40-мм зброя «Бофорс» (довжина ствола 60 калібрів), розміщена на установці AN 4-40, розробленої австралійською державною збройовою компанією.Ця АУ забезпечує високу точність стрілянини зброї навіть у штормових умовах. Її скорострільність 120 вистр. / хв., а дальність стрілянини – 10 км. До складу озброєння катера входить також 81 мм міномет. Крім того, передбачено місця для встановлення трьох 12,7-мм кулеметів «Браунінг» М2. Планувалося, що до 2003 року катери типу «Фрімантл» будуть замінені такою самою кількістю нових ПКА.Однак початок надходження ПКА типу «Армідейл» до складу флоту було відкладено на кінець 2004 – початок 2005 років, що призвело до продовження термінів служби катерів типу «Фрімантл» далеко за межі запланованих термінів виведення з бойового складу.