  Based on the combinatorial interpretation of the ordered Bell numbers, which
count all the ordered partitions of the set $[n]=\{1,2,\dots,n\}$, we introduce
the Fibonacci partition as a Fibonacci permutation of its blocks. Then we
define the Fibonacci-Fubini numbers that count the total number of Fibonacci
partitions of $[n]$. We study the classical properties of this sequence
(generating function, explicit and Dobi\'nski-like formula, etc.), we give
combinatorial interpretation, and we extensively examine the Fibonacci-Fubini
arithmetic triangle. We give some associate linear recurrence sequences, where
in some sequences the Stirling numbers of the first and second kinds appear as
well.
