Following https://gajim.org/downloads.php?lang=en#ubuntu on Ubuntu 16.04 I get:

% sudo apt-get install gajim-nightly 
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies.
 gajim-nightly : Depends: gir1.2-gtk-3.0 (>= 3.22) but 3.18.9-1ubuntu3.3 is to be installed
                 Depends: python3-precis-i18n but it is not installable
                 Recommends: python3-gnupg (>= 0.3.8) but it is not going to be installed

% aptitude show python3-precis-i18n
No current or candidate version found for python3-precis-i18n
Package: python3-precis-i18n
State: not a real package

Should this be working?

If 16.04 is not supported (even though it's official end-of-life is in 2021), then I think it should say that on the install instructions.