Её название может происходить от валлийского слова «Шаблон:Lang», означающего «царапать». По легендам она появлялась на острове Англси, где убила и съела девять воинов. В «Триадах острова Британия» (Шаблон:Lang-cy) эта кошка считается потомством огромной демонической свиньи Хенвен, и утверждается, что после рождения она была выброшена в море с целью утопления. Выжив, она доплыла до Англии, где сыновья Палуга нашли и взяли её, не понимая её смертоносного начала. Сбежав, она посеяла хаос на острове, пока не была убита сэром Кеем. В других вариантах легенды её победил сам Король Артур.
Ещё одна легенда неизвестного происхождения связывает кошку с Мон-дю-Шат в Савойе, Франция, недалеко от Женевского озера, где Артур якобы потерпел поражение от кошки в бою, который проходил в болотах близ этой горы. Стоит отметить, что на сегодняшний день легенда о кошке Палуга в гораздо большей степени популярна во Франции, нежели в Великобритании.
Иногда кошка Палуга упоминается в околонаучных криптозоологических отчётах о так называемых британских больших кошках.