Patschinski's new club was FC St. Pauli where he would have his biggest success in the next three years.
Im Jahr 2000 schließlich kam Patschinski zum FC St. Pauli, mit dem er in den folgenden drei Jahren seine größten Erfolge erreichte.