We will discuss a connection between OPE algebras appearing in celestial holography for various theories and the `colour-kinematics duality' in the bulk spacetime description of those theories. Both the celestial algebras and the colour-kinematics duality take a particularly simple form for self-dual Yang-Mills and gravity. In particular, we show that the $Lw_{1+\infty}$ celestial algebra recently unveiled in self-dual gravity arises from the soft expansion of an area-preserving diffeomorphism algebra, which plays the role of the kinematic algebra in the colour-kinematics duality. We also present deformations of the celestial algebras resulting from Moyal deformations of the self-dual theories, e.g. the deformation of $Lw_{1+\infty}$ into $LW_{1+\infty}$ in the case of self-dual gravity. In addition, we discuss the relation of these deformations to higher-spin theories of massless particles that can be thought of as extensions of self-dual Yang-Mills and gravity. Finally, we present a proof that tree-level scattering amplitudes in the theories we focus on vanish, signalling their classical integrability, which is an S-matrix version of the Ward conjecture for integrable systems.