Let \(\{a_j\), \(j\geq 0\}\) be a sequence of real numbers, and consider the sequence \(\{V_n\), \(n=0,\pm 1,\pm 2,\dots\}\) defined by the following infinite order linear recurrence relation \[ V_{n+1}= a_0V_n+ a_1V_{n-1}+\cdots+ a_m V_{n-m}+\cdots \quad\text{for }n\geq 0, \tag \(*\) \] where \(\{V_j\), \(j\leq 0\}\) are specified by initial conditions. Such sequences are called \(\infty\)-generalized Fibonacci sequences. The aim of this paper is to study the connection between sequences \((*)\) and the properties of suitably defined Markov chains when the coefficients are nonnegative. In order to ensure the existence of \(V_n\) for any \(n\geq 1\), some basic hypotheses on the sequences \(\{a_j\), \(j\geq 0\}\) and \(\{V_j\), \(j\leq 0\}\) are necessary. The case \(\sum_{j\geq 0}a_j=1\) allows for a simple interpretation of \((*)\) by means of an associated homogeneous Markov chain.