Sachverhalt: A. Am 14. Mai 2013 erteilte der Gemeinderat Niederhasli A._ und B._ die nachträgliche baurechtliche Bewilligung für ein eigenmächtig erstelltes Gartenhaus auf dem Grundstück Kat.-Nr. "..." an der X._strasse in Niederhasli unter Bedingungen und Auflagen. Am 24. Juni 2013 erhoben A._ und B._ Rekurs beim Baurekursgericht des Kantons Zürich und beantragten, der Entscheid des Gemeinderats Niederhasli sei ganz oder teilweise aufzuheben. Am 19. Dezember 2013 wies das Baurekursgericht den Rekurs ab, soweit es darauf eintrat. B. Dagegen führten A._ und B._ Beschwerde beim Verwaltungsgericht des Kantons Zürich, wobei sie beantragten, den Entscheid des Baurekursgerichts aufzuheben, soweit dieser bestimmte Teile des baurechtlichen Entscheids des Gemeinderats Niederhasli bestätige; eventuell sei die Sache zur Neubeurteilung an das Baurekursgericht zurückzuweisen. Am 21. Januar 2016 wies das Verwaltungsgericht die Beschwerde ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 22. April 2016 an das Bundesgericht beantragen A._ und B._, das Urteil des Verwaltungsgerichts und damit die strittigen Teile des baurechtlichen Entscheids des Gemeinderates aufzuheben; eventuell sei das Urteil des Verwaltungsgerichts aufzuheben und die Sache zur Ergänzung und Neubeurteilung an dieses zurückzuweisen. In prozessualer Hinsicht wurde um Erteilung der aufschiebenden Wirkung ersucht. Der Gemeinderat Niederhasli schliesst auf Abweisung der Beschwerde und verlangt ausdrücklich die Zusprechung einer Parteientschädigung. Das Verwaltungsgericht stellt Antrag auf Abweisung der Beschwerde, soweit darauf einzutreten sei. A._ und B._ äusserten sich am 6. Juli 2016 nochmals zur Sache. D. Mit verfahrensleitender Verfügung vom 24. Mai 2016 erteilte der Präsident der I. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung.