It is well known that the Young lattice is the Bratelli diagram of the symmetric groups expressing how irreducible representations restrict from $S_N$ to $S_{N-1}$. In 1988, Stanley discovered a similar lattice called the Young-Fibonacci lattice which was realized as the Bratelli diagram of a family of algebras by Okada in 1994. In this paper, we realize the Okada algebra and its associated monoid using a labeled version of Temperley-Lieb arc-diagrams. We prove in full generality that the dimension of the Okada algebra is $n!$. In particular, we interpret a natural bijection between permutations and labeled arc-diagrams as an instance of Fomin's Robinson-Schensted correspondence for the Young-Fibonacci lattice. We prove that the Okada monoid is aperiodic and describe its Green relations. Lifting those results to the algebra allows us to construct a cellular basis of the Okada algebra. }