Let $Σ_{A}$ be a topologically mixing shift of finite type, let $σ:Σ_{A}\toΣ_{A}$ be the usual left-shift, and let $μ$ be the Gibbs measure for a Hölder continuous potential that is not cohomologous to a constant. In this paper we study recurrence rates for the dynamical system $(Σ_{A},σ)$ that hold $μ$-almost surely. In particular, given a function $ψ:\mathbb{N}\to \mathbb{N}$ we are interested in the following set $$R_ψ=\{{\texttt i}\in Σ_{A}:i_{n+1}\ldots i_{n+ψ(n)+1}=i_1\ldots i_{ψ(n)}\textrm{ for infinitely many }n\in\mathbb{N}\}.$$ We provide sufficient conditions for $μ(R_ψ)=1$ and sufficient conditions for $μ(R_ψ)=0$. As a corollary of these results, we discover a new critical threshold where the measure of $R_ψ$ transitions from zero to one. This threshold was previously unknown even in the special case of a non-uniform Bernoulli measure defined on the full shift. The proofs of our results combine ideas from Probability Theory and Thermodynamic Formalism. In our final section we apply our results to the study of dynamics on self-similar sets.